<?
include_once "SortHelper/SortHelper.php";
/**
 * 快速排序 1
 */

/**
 * 3、对arr[l...r]部分进行partition操作
 * 返回P,使得arr[l...p-1] < arr[p]; arr[p+1...r] > arr[p]
 */
function _partition(&$arr, $l, $r)
{
    /**
     * 随机在arr[l...r]的范围中，选择一个数值作为标定点
     * 然后把这个随机数和第一个元素进行交换
     * 然后选择最左边的的元素作为标定点 左边的元素 < v < 右边的元素
     */
    $rand_index = rand() % ($r - $l + 1) + $l;
    SortHelper::swap($arr, $l, $rand_index);

    //使用最左侧的元素
    $v = $arr[$l];

    //arr[l+1...j] < v; arr[j+1...i) > v'
    $j = $l;//初始化都从最左边开始
    for ($i = $l+1; $i <= $r; $i++) { 
        /**
         * 如果查到的元素 < v ,就交换 i 和 j 的值
         * 然后 j++
         */
        if ($arr[$i] < $v) {
            SortHelper::swap($arr, $i, $j + 1);
            $j++;
        }
    }

    //最后把最左边的元素 l 和 j 元素交换就得到了排好序的数组（小于v < v < 大于v）
    SortHelper::swap($arr, $l, $j);
    return $j;
}

//2、递归调用对arr[l...r]的范围进行排序
function quick_sort(&$arr, $l, $r)
{
    if ($l >= $r) {
        return;    
    }
    $p = _partition($arr, $l, $r);

    quick_sort($arr, $l, $p - 1);
    quick_sort($arr, $p + 1, $r);
}

//快速排序 1、主方法
function quickSort(&$arr)
{
    $arr_len = count($arr);
    if ($arr_len <= 0) {
        return [];
    }
    quick_sort($arr, 0, $arr_len - 1);
}


$arr = [100,4,6,2,59,67,57,45,71,82];
quickSort($arr);
for ($i=0; $i < count($arr); $i++) { 
    echo $arr[$i].', ';
}
